package src.CodeTop;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 */

public class _215KthLargestElementInAnArray {
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int target = findKthLargest1(nums, k);
        System.out.println(target);
    }

    /**
     * 使用Java已经实现的堆
     * @param nums 数组
     * @param k 第k个
     * @return 第k个元素
     */
    public static int findKthLargest1(int[] nums, int k) {
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topEle = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }

    /**
     * 手写堆排序
     * @param nums 要排序的数组
     * @param k 第k位
     * @return 第k位元素
     */
    public static int findKthLargest2(int[] nums, int k) {
        heapSort(nums);
        return nums[nums.length - k];
    }

    /**
     * 堆排序
     * @param nums 要排序的数组
     */
    public static void heapSort(int[] nums) {
        // 中间临时变量
        int temp = 0;
        // 将无序序列构建成一个堆 根据升序降序需求选择大顶堆小顶堆
        // 寻找倒数第一个非叶子结点
        for (int i = nums.length / 2 - 1 ; i >= 0 ; i--) {
            adjustHeap(nums, i, nums.length);
        }
        // 将堆顶元素与末尾元素交换 将最大元素沉到数组末端
        // 重新调整结构 使其满足堆定义 然后继续交换堆顶元素与当前末尾元素 反复执行调整+交换步骤 直到整个序列有序
        for (int j = nums.length - 1 ; j > 0 ; j--) {
            //交换
            temp = nums[j];
            nums[j] = nums[0];
            nums[0] = temp;
            adjustHeap(nums, 0, j);
        }
    }

    /**
     * 将一个数组(二叉树)，调整为大顶堆
     * 功能:完成i索引对应的非叶子结点树调整为大顶堆
     * 举例:{4, 6, 8, 5, 9} => i=1 => adjustHeap => {4 9 8 5 6}
     * 再次调用 => i=0 => {9 6 8 5 4}
     * @param nums 待调整的数组
     * @param i 表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素在逐步的调整，length是在逐步地减少的
     */
    public static void adjustHeap(int[] nums, int i, int length) {
        // 将当前元素的值保存到副本中，最后要使用
        int temp = nums[i];
        // 开始调整，从i对应的左子节点开始
        for (int k = i * 2 + 1 ; k < length ; k = k * 2 + 1) {
            // 如果左子节点的值小于右子结点的值(此时还要判别k+1<length，因为越界了就不用比较了)
            if ((k + 1 < length) && nums[k] < nums[k + 1]) {
                // 将当前指针指向右子结点
                k++;
            }
            // 此时，指针已经指向了左右子结点中大的一个
            if (nums[k] > temp) {// 如果子结点大于父结点
                // 将较大的值赋值给父结点
                nums[i] = nums[k];
                // 将k赋值给i，将原父结点的值赋值给被改变的子结点
                i = k;
            }else {
                break;
            }
            // 当for循环结束后 我们已经将以i为父结点的这棵树的最大值放在了最顶上(局部)
            // 将temp值放到调整后的位置
            nums[i] = temp;
        }
    }
}
